# 168. 最大乘积(好题)
# https://www.lanqiao.cn/problems/169/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/13

def get_max_product_greed(n, k, arr):
    """贪心算法
    考虑k为奇数和偶数两种情况:
    k为奇数:
        1. 若最大数为正数，先选取该数以保证乘积最大。然后进入k为偶数的情况.
        2. 若最大数为负数或零，说明整个数组元素非正，且结果必定为负数, 此时选取最右边的 K 个数（绝对值最小，乘积最大负数）。
    k为偶数:
        每次比较左端和右端的两个数的乘积，选择较大者，直到选完所有数。
    """

    def mod(x):
        if x < 0:
            return -((-x) % int(1e9 + 9))
        return x % int(1e9 + 9)

    arr.sort()
    l, r = 0, n - 1
    res = 1.0

    # k为奇数时
    if k % 2 == 1:
        if arr[-1] > 0:  # 最大的数字为正数
            res *= arr[-1]
            k -= 1
            r -= 1
        else:  # 所有数字均为负数
            for i in range(k):
                res *= arr[n - 1 - i]
                res = mod(res)
            return res

    # k为偶数时
    while k > 0:
        prod_l = arr[l] * arr[l + 1]
        prod_r = arr[r] * arr[r - 1]
        if prod_l > prod_r:
            res *= prod_l
            l += 2
        else:
            res *= prod_r
            r -= 2
        k -= 2
        res = mod(res)

    return int(res)


if __name__ == '__main__':
    # n, k = map(int, input().split())
    # inp = []
    # for i in range(n):
    #     inp.append(int(input()))

    print(get_max_product_greed(5, 3, [-100000, -10000, 2, 100000, 10000]))  # 999100009

    with open("../data/169.in", "r") as file:
        n, k = map(int, file.readline().split())
        inp = []
        for i in range(n):
            inp.append(int(file.readline()))
    print(get_max_product_greed(n, k, inp))  # 984521156
